EP1 - CALCULO DO CONJUNTO DE MANDELBROT EM PARALELO COM PTHREADS E OPENMP

Alunos

Descrição dos experimentos

Foram realizadas 10 medições para cada cenário do programa sequencial. As variações incluíram modificar a imagem gerada e o seu tamanho (uma potência de 2 entre $2^{4}$ e $2^{13}$).

Além dos mesmos experimentos feitos na versão sequencial, também foram realizados experimentos alterando o número de threads (uma potência de 2 entre $2^{0}$ e $2^{5}$). As bibliotecas utilizadas foram Pthreads e OpenMP.

As visualizações foram criadas com seus devidos intervalos de confiança de 95% segundo a distribuição T Student com 9 graus de liberdade, dado o pequeno valor da amostra coletada para os experimentos.

O computador utilizado para executar os experimentos possui um processador Intel(R) Xeon(R) CPU E5-2670 0 @ 2.60GHz de 32 núcleos, 64GB de memória RAM e sistema operacional Debian 4.19.171-2.

Análises e gráficos

Para começar a análise dos dados e sua visualização, precisamos importar as bibliotecas conforme comando abaixo:

Os resultados dos experimentos se encontram no arquivo results.tsv, que vamos armazenar em um dataframe df.

Transformando em categóricas algumas colunas que estão como numéricas

Para responder às primeiras perguntas, utilizaremos os dados sem impacto de alocação de memória e IO.

Como e por que as três versões do programa se comportam com a variação:

Do tamanho da entrada?

Para analisar o comportamento dos algoritmos em função do tamanho da entrada, vamos fixar os seguintes parâmetros:

Os gráficos apresentam o tempo de execução em função do tamanho da entrada, utilizando 1, 2, 4, 8, 16 e 32 threads, na região full. Uma entrada de tamanho N produz como resultado de uma imagem de dimensões N x N. Para computar o conjunto de Mandelbrot, realizamos operações para cada pixel da imagem. Portanto, para uma imagem de tamanho N x N, a complexidade do algoritmo é O(N²). Podemos observar esse comportamento no formato dos gráficos, que descrevem uma função quadrática.

No experimento com apenas uma thread os três algoritmos se comportam de forma muito semelhante em relação ao tamanho da entrada, variando no máximo 0.52s, e na média 0.03s. Dos outros cinco gráficos podemos depreender que o número de threads, apesar de reduzir o tempo de execução total, não muda a complexidade do algoritmo, e portanto não altera o formato dos gráficos em relação ao tamanho da entrada.

Os gráficos acima exibem o número de instruções em função do tamanho da entrada, utilizando 1, 2, 4, 8, 16 e 32 threads, na região full. Da mesma forma que o tempo de execução, o número de instruções cresce quadraticamente à medida que o tamanho da entrada aumenta. Também observamos que, com uma única thread, os algoritmos se comportam igualmente.

Nos gráficos dos experimentos com 16 e 32 threads fica visível a diferença no número de instruções executadas com Pthreads e OpenMP. Isso ocorre pois a biblioteca PThreads é de baixo nível, permitindo um controle mais refinado das instruções executadas, enquanto o OpenMP é um nível de abstração a mais, que pode gerar um código menos otimizado para a situação concreta.

Das regiões do Conjunto de Mandelbrot?

Veremos o comportamento dos algoritmos em diferentes tamanho de imagem, levando em consideração as diferentes regiões do conjunto de Mandelbrot.

Através dos gráficos acima é possível concluir que, para o menor tamanho de imagem, não há muita diferença entre os tempos em regiões diferentes. O interessante é notarmos que quanto mais threads, pior tende a ser o desempenho, dado que o overhead se torna maior que o ganho ao paralelizar o processamento.

Com o aumento no tamanho da imagem para 64x64, já é possível analisar uma mudança no comportamento entre diferentes regiões. A região Full possui um tempo menor, enquanto a região Triple Spiral costuma levar mais tempo para processar. Isso se deve à diferença no número de iterações necessários para a convergência em cada região.

Os gráficos levando em consideração o maior tamanho de imagem só corroboram o comportamento visto anteriormente. O impacto no número de threads fica ainda mais visível.

Do número de threads?

Aqui iremos utilizar a mesma metodologia gráfica para mostrar o comportamento de cada algoritmo de acordo com o número de threads utilizado.

Através do gráfico acima que mostra como as variações do tamanho das imagens e a quantidade de threads impactam o tempo de execução dos algoritmos na imagem Full, podemos perceber uma relação inversamente proporcional entre threads e tempo.

Ao observamos o comportamento da linha azul que representa uma única thread, percebemos que não há diferença notável entre os três algoritmos, uma vez que com apenas uma thread executamos os algoritmos paralelos de maneira análoga ao sequencial. Da mesma maneira, a criação de um número grande de threads para pequenos tamanhos de entrada também não se mostra muito vantajosa em relação ao programa sequencial. Podemos observar claramente esse efeito ao olharmos o começo do comportamento da linha vermelha representando 32 threads nos algortimos mandelbrot_pth e mandelbrot_omp.

Ademais, apartando essas casos específicos vemos, como já era esperado, que ao aumentarmos o número de threads, mais rápida é a execução do programa e que com o aumento do tamanho de entrada, maior é o tempo. Dessa maneira, para termos um bom desempenho em relação ao tempo de execução, ao aumentarmos o tamanho, precisamos aumentar o número de threads, impacto que fica evidente ao olharmos a parte final dos gráficos: maiores tamanhos com maior número de threads resultam nos menores tempos encontrados.

Apenas para efeito de visualização, plotamos também o mesmo gráfico para a imagem Triple Spiral que é a região que apresentou maior tempo de execução. Nele podemos ver que os mesmos comportamentos descritos anteriormente ainda valem e que isso é independente da imagem que escolhemos.

Qual o impacto das operações de I/O e alocação de memória no tempo de execução?

Compararemos o tempo de execução do algoritmo sequencial em cada uma das regiões da imagem nos casos em que ambos I/O e alocação de memória são realizados e nos casos em que nenhuma dessas operações é feita.

Os gráficos acima mostram, para cada região da imagem, a proporção do tempo consumido pela alocação de memória e pelo I/O em comparação com o tempo gasto por todo o algoritmo.

Observa-se que para tamanhos de imagem pequenos, o tempo gasto pela alocação de memória e por I/O corresponde à maior parte de toda execução do algoritmo. No entanto, com o aumento do tamanho, a alocação de memória e I/O passam a representar uma porcentagem bem menor em relação às outras operações.

Agora, novamente para cada imagem, compararemos o tempo absoluto gasto pelo mesmo algoritmo sequencial nos casos em que há alocação de memória e I/O e nos casos em que não há.

A partir de todos os gráficos apresentados, pode-se concluir que o impacto das operações de I/O e alocação de memória é muito mais perceptível em termos percentuais quando o tamanho das imagens é pequeno. Isso ocorre pois, nesse caso, os custos de alocação de memória e escrita de arquivo - mesmo que baixos do ponto de vista absoluto - excedem os das outras operações performadas.

Quando o tamanho das imagens aumenta, há um impacto menor percentualmente - dado que nesse caso o tempo de execução das outras operações supera o tempo para alocar memória e realizar as operações de I/O -, porém maior absolutamente, uma vez que a memória a ser alocada é muito maior e, consequentemente, o arquivo a ser escrito também.

Conclusões

Os experimentos evidenciaram que as bibliotecas PThread e OpenMP podem resultar em ganhos de performance robustos. No entanto, devemos observar caso a caso, pois a paralelização do código gera overhead, e não é vantajosa para pequenos tamanhos de entrada. Também temos que levar em consideração o impacto das operações de alocação de memória e IO, pois elas podem ser um gargalo na performance do algoritmo. A biblioteca OpenMP possui uma facilidade maior de implementação comparada à PThread, porém um menor nível de customização. Desta forma, devemos analisar este custo benefício para cada situação.